package com.acwing.partition4;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * @author `RKC`
 * @date 2022/1/24 11:54
 */
@SuppressWarnings("all")
public class AC356次小生成树 {

    private static final int N = 100010, M = 300010, D = (int) (Math.log(N) / Math.log(2)), INF = 0x3f3f3f3f;
    private static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    private static int[] depth = new int[N], parent = new int[N];
    private static int[][] f = new int[N][D + 1], dist1 = new int[N][D + 1], dist2 = new int[N][D + 1];
    //dist用于缓存一条边两个点的边权，用于后续计算最大值和次大值
    private static int[] dist = new int[2 * N];

    private static int n = 0, m = 0, idx = 0;
    private static Queue<Integer> queue = new ArrayDeque<>(N);
    private static Edge[] edges = new Edge[M];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 0; i <= n; i++) h[i] = -1;
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split(" ");
            int a = Integer.parseInt(s[0]), b = Integer.parseInt(s[1]), c = Integer.parseInt(s[2]);
            edges[i] = new Edge(a, b, c, false);
        }
        //求最小生成树，并根据MST进行建图
        long sum = kruskal();
        //bfs进行LCA的预处理，处理出f和depth数组
        bfs();
        //枚举每一条非树边，尝试将该边加入MST得到次小生成树
        long ans = (long) 1e18;
        for (int i = 0; i < m; i++) {
            if (!edges[i].flag) {
                int u = edges[i].u, v = edges[i].v, w = edges[i].w;
                //lca返回加入该边后相比MST新增的权值大小
                ans = Math.min(ans, sum + lca(u, v, w));
            }
        }
        writer.write(ans + "\n");
        writer.flush();
    }

    private static void bfs() {
        queue.add(1);
        depth[1] = 1;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int i = h[u]; i != -1; i = ne[i]) {
                int v = e[i];
                if (depth[v] != 0) continue;
                depth[v] = depth[u] + 1;
                f[v][0] = u;
                dist1[v][0] = w[i];
                dist2[v][0] = -INF;
                for (int j = 1; j <= D; j++) {
                    int anc = f[v][j - 1];
                    f[v][j] = f[anc][j - 1];
                    //当前节点跳到中间节点anc，中间节点anc跳到LCA节点，最大和次大一共4个距离，预处理出来赋值给dist1和dist2
                    int[] dist = new int[]{dist1[v][j - 1], dist2[v][j - 1], dist1[anc][j - 1], dist2[anc][j - 1]};
                    dist1[v][j] = dist2[v][j] = -INF;
                    //从dist数组中找到最大和次大
                    for (int val : dist) {
                        if (val > dist1[v][j]) {
                            dist2[v][j] = dist1[v][j];
                            dist1[v][j] = val;
                        } else if (val != dist1[v][j] && val > dist2[v][j]) {
                            dist2[v][j] = val;
                        }
                    }
                }
                queue.add(v);
            }
        }
    }

    private static int lca(int x, int y, int w) {
        int idx = 0;
        if (depth[x] < depth[y]) {
            int t = x;
            x = y;
            y = t;
        }
        for (int i = D; i >= 0; i--) {
            if (depth[f[x][i]] >= depth[y]) {
                //记录沿途中的最大和次大
                dist[idx++] = dist1[x][i];
                dist[idx++] = dist2[x][i];
                x = f[x][i];
            }
        }
        if (x != y) {
            for (int i = D; i >= 0; i--) {
                if (f[x][i] != f[y][i]) {
                    dist[idx++] = dist1[x][i];
                    dist[idx++] = dist1[y][i];
                    dist[idx++] = dist2[x][i];
                    dist[idx++] = dist2[y][i];
                    x = f[x][i];
                    y = f[y][i];
                }
            }
            //加入最后一跳到LCA的距离
            dist[idx++] = dist1[x][0];
            dist[idx++] = dist1[y][0];
        }
        //从dist中找到最大值和次大值
        int d1 = -INF, d2 = -INF;
        for (int i = 0; i < idx; i++) {
            if (dist[i] > d1) {
                d2 = d1;
                d1 = dist[i];
            } else if (d1 != dist[i] && dist[i] > d2) {
                d2 = dist[i];
            }
        }
        //返回加入该边后的增量
        if (w > d1) return w - d1;
        if (w > d2) return w - d2;
        return INF;
    }

    private static long kruskal() {
        Arrays.sort(edges, 0, m, (o1, o2) -> Integer.compare(o1.w, o2.w));
        long sum = 0;
        for (int i = 0; i <= n; i++) parent[i] = i;
        for (int i = 0; i < m; i++) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            int a = find(u), b = find(v);
            if (a != b) {
                sum += w;
                parent[a] = b;
                add(u, v, w);
                add(v, u, w);
                edges[i].flag = true;
            }
        }
        return sum;
    }

    private static int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }

    private static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx;
        w[idx++] = c;
    }

    private static class Edge {
        private int u, v, w;
        private boolean flag;

        public Edge(int a, int b, int c, boolean f) {
            u = a;
            v = b;
            w = c;
            flag = f;
        }
    }
}
